package maxsumarrayafternegations1005

import "sort"

// 对nums中的数进行k次取反操作，
// 使得nums的和最大，返回最大值
// 例如，nums = [4,2,3], k = 1
// 取反后，nums = [4,-2,3]，和为5
// 注意：可以对同一个数进行多次取反操作
// 例如，nums = [4,2,3], k = 2
// 第一次对位置0取反后，nums = [-4,2,3]；第二次仍然对位置0取反，nums = [4,2,3]，和为9
// 思路：
// 1. 先对nums进行排序，
// 2. 然后逐次进行取反操作，如果当前的数是负数，则k--，
// 3. 如果此时k为0，则结束循环；如果此时k大于0，则重新排序
// 4. 如果当前的数是正数，当k为奇数时，取反当前的数；当k为偶数时，不取反
// 5. 最后返回nums的和
func LargestSumAfterKNegations(nums []int, k int) int {
	// 1. 先对nums进行排序
	sort.Ints(nums)
	// 2. 然后逐次进行取反操作，如果当前的数是负数，则k--，
	for i := 0; i < len(nums); i++ {
		if nums[i] < 0 && k > 0 {
			nums[i] = -nums[i]
			k--
		}
	}
	// 3. 如果此时k为0，则结束循环；如果此时k大于0，则重新排序
	if k > 0 {
		sort.Ints(nums)
		if k%2 == 1 {
			nums[0] = -nums[0]
		}
	}
	// 4. 最后返回nums的和
	sum := 0
	for _, num := range nums {
		sum += num
	}
	return sum
}
